The present invention relates generally to a differential lossless compression method and system and more particularly to a method of and system for encoding instruction bit patterns using a primary dictionary for the most frequently occurring bit patterns and encoding the remaining instruction bit patterns using the differences between the remaining bit patterns and the bit patterns that are already encoded in the primary dictionary.
In order to reduce the amount of memory needed to store data processing instructions in on-chip SRAM memory, the instructions are typically compressed to reduce the amount of memory that must be stored. Typical compression algorithms involve storing data words used in an instruction set in a look-up table and accessing the data words through the use of code words that identify the address at which the desired data word is stored. While this type of compression reduces the amount of memory needed compared to storing all of the necessary data words, it still requires a great amount of memory to operate properly.
The present invention provides a method of and system for performing lossless compression in which the most frequently accessed data words are stored in a primary dictionary and in which shortened code words are used to access these data words. Difference dictionaries are used to store difference bit streams which are accessed by code words which identify a data word in the primary dictionary and a difference bit stream in one of the difference dictionaries. An exclusive-OR operation is performed on the identified data word and the difference bit stream to calculate a decoded data word that is not stored in either the primary or difference dictionaries.
According to one aspect of the invention, a method of decompressing data words of an instruction set includes:
A. filling a primary dictionary with at least one primary data word of the instruction set, each of the at least one primary data word being stored in the primary dictionary in a location associated with a distinct primary dictionary index;
B. filling at least one secondary dictionary with at least one difference bit stream, each of the at least one difference bit stream being stored in one of the at least one secondary dictionary in a location associated with a distinct secondary dictionary index;
C. receiving a code word, the code word comprising:
a. a header which identifies the primary dictionary and a specific one of the at least one secondary dictionary;
b. a first bit stream; and
c. a second bit stream;
wherein the first bit stream comprises the distinct primary dictionary index and the second bit stream comprises the distinct secondary dictionary index;
D. retrieving the primary data word stored at the location in the primary dictionary location associated with the distinct primary dictionary index;
E. retrieving the difference bit stream stored at the location in the at least one secondary dictionary location associated with the distinct secondary dictionary index; and
F. performing a logic operation on the primary data word and the difference bit stream to obtain a resultant data word that is not stored in either the at least one primary dictionary or the at least one secondary dictionary.
The primary data words may include 32 bit words, the code words may include less than 32 bits, the first bit stream may include up to 11 bits and the second bit stream may include at least 5 bits. The logic operation may be an exclusive-OR operation. The at least one secondary dictionary may include a first secondary dictionary which includes difference bit streams which are more commonly included in the second bit stream of the code word and a second secondary dictionary which includes difference bit streams which are less commonly included in the second bit stream of the code word.
According to another aspect of the invention, a system for decompressing data words of an instruction set includes:
a computer processor which performs operations based on the instruction sets;
a memory device including:
A. a primary dictionary including at least one primary data word of the instruction set, each of the at least one primary data word being stored in the primary dictionary in a location associated with a distinct primary dictionary index; and
B. at least one secondary dictionary including at least one difference bit stream, each of the at least one difference bit stream being stored in one of the at least one secondary dictionary in a location associated with a distinct secondary dictionary index; and
a decompression engine for receiving a code word from the computer processor and accessing the memory device to decode the code word to obtain a data word requested by the computer processor;
wherein the code word includes:
a. a header which identifies the primary dictionary and a specific one of the at least one secondary dictionary;
b. a first bit stream; and
c. a second bit stream;
wherein the first bit stream comprises the distinct primary dictionary index and the second bit stream comprises the distinct secondary dictionary index; and
wherein the decompression engine retrieves the primary data word stored at the location in the primary dictionary location associated with the distinct primary dictionary index;
retrieves the difference bit stream stored at the location in the at least one secondary dictionary location associated with the distinct secondary dictionary index; and
performs a logic operation on the primary data word and the difference bit stream to obtain a resultant data word that is not stored in either the at least one primary dictionary or the at least one secondary dictionary, the resultant data word being the data word requested by the computer processor.
According to another aspect of the invention, a system for decompressing data words of an instruction set includes:
a computer processor which performs operations based on the instruction sets;
a memory device including:
A. a primary dictionary including at least one primary data word of the instruction set, each of the at least one primary data word being stored in the primary dictionary in a location associated with a distinct primary dictionary index; and
B. a first secondary dictionary including at least one difference bit stream, each of the at least one difference bit stream being stored in the first secondary dictionary in a location associated with a distinct first secondary dictionary index; and
C. a second secondary dictionary including at least one difference bit stream, each of the at least one difference bit stream being stored in the second secondary dictionary in a location associated with a distinct second secondary dictionary index; and
a decompression engine for receiving a code word from the computer processor and accessing the memory device to decode the code word to obtain a data word requested by the computer processor;
wherein the code word includes:
a. a header which identifies the primary dictionary and one of the first secondary dictionary and the second secondary dictionary;
b. a first bit stream; and
c. a second bit stream;
wherein the first bit stream comprises the distinct primary dictionary index and the second bit stream comprises the distinct secondary dictionary index for the secondary dictionary identified in the header; and
wherein the compression engine retrieves the primary data word stored at the location in the primary dictionary location associated with the distinct primary dictionary index, retrieves the difference bit stream stored at the location in the identified secondary dictionary location associated with the distinct secondary dictionary index; and
performs an exclusive-OR operation on the primary data word and the difference bit stream to obtain a resultant data word that is not stored in either the primary dictionary or the at least one secondary dictionary, the resultant data word being the data word requested by the computer processor.
According to yet another aspect of the invention, a system for decompressing data words of an instruction set includes:
processing means for performing operations based on the instruction sets;
a memory means including:
A. a primary dictionary including at least one primary data word of the instruction set, each of the at least one primary data word being stored in the primary dictionary in a location associated with a distinct primary dictionary index; and
B. a first secondary dictionary including at least one difference bit stream, each of the at least one difference bit stream being stored in the first secondary dictionary in a location associated with a distinct first secondary dictionary index; and
C. a second secondary dictionary including at least one difference bit stream, each of the at least one difference bit stream being stored in the second secondary dictionary in a location associated with a distinct second secondary dictionary index; and
decompression means for receiving a code word from the computer processor and accessing the memory device to decode the code word to obtain a data word requested by the computer processor;
wherein the code word includes:
a. a header which identifies the primary dictionary and one of the first secondary dictionary and the second secondary dictionary;
b. a first bit stream; and
c. a second bit stream;
wherein the first bit stream comprises the distinct primary dictionary index and the second bit stream comprises the distinct secondary dictionary index for the secondary dictionary identified in the header; and
wherein the decompression means retrieves the primary data word stored at the location in the primary dictionary location associated with the distinct primary dictionary index, retrieves the difference bit stream stored at the location in the identified secondary dictionary location associated with the distinct secondary dictionary index; and
performs an exclusive-OR operation on the primary data word and the difference bit stream to obtain a resultant data word that is not stored in either the primary dictionary or the at least one secondary dictionary, the resultant data word being the data word requested by the computer processor.